package 哈希;
import java.util.*;
/**
 * 将字符串数组中的字母异位词分组
 * 时间复杂度O(n * k * log k)，空间复杂度O(n * k)，n为字符串数组长度，k为字符串的最大长度
 */
public class groupAnagrams {
    /**
     * 将字符串数组中的字母异位词分组
     * 
     * @param strs 输入字符串数组
     * @return 分组后的字母异位词列表
     */
    public List<List<String>> groupAnagramsM(String[] strs){
        HashMap<String, List<String>> map = new HashMap<>(); // 用于存储分组结果
        for(String str : strs){ // 遍历输入字符串数组
            char[] arr = str.toCharArray(); // 将字符串转换为字符数组
            Arrays.sort(arr); // 对字符数组进行排序
            String cur = new String(arr); // 将排序后的字符数组转换回字符串
            List<String> list = map.getOrDefault(cur, new ArrayList<>()); // 获取当前字符串的分组列表
            list.add(str); // 将当前字符串加入分组列表
            map.put(cur, list); // 更新分组结果
        }
        return new ArrayList<>(map.values()); // 返回分组后的字母异位词列表
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行字符串，用空格分隔，表示输入字符串数组
     * 例如：eat tea tan ate nat bat 表示一个输入字符串数组
     * 输出格式：分组后的字母异位词列表
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(" "); // 读取输入并分割
        groupAnagrams ga = new groupAnagrams(); // 创建实例
        System.out.println(ga.groupAnagramsM(strs)); // 输出分组后的字母异位词列表
        sc.close(); // 关闭输入流
    }
}
